package learnjava.interview;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Allorder {
    static void all_order(String in,String stack,String out)
    {
        if(in.equals("")&&stack.equals(""))
            System.out.println(out);
        if(!in.equals(""))
            all_order(in.substring(1),stack+in.charAt(0),out);
        if(!stack.equals(""))
            all_order(in,stack.substring(0,stack.length()-1),out+stack.charAt(stack.length()-1));
    }

    static <T> void all_order(LinkedList<T> in, LinkedList<T> stack, LinkedList<T> out){
        if(in.isEmpty()&&stack.isEmpty())
            System.out.println(out);
        if(!in.isEmpty()){
            LinkedList<T> newIn = new LinkedList<>(in);
            LinkedList<T> newStack = new LinkedList<>(stack);
            LinkedList<T> newOut = new LinkedList<>(out);
            newStack.offerLast(newIn.pollFirst());
            all_order(newIn,newStack,newOut);
        }
        if(!stack.isEmpty()) {
            LinkedList<T> newIn = new LinkedList<>(in);
            LinkedList<T> newStack = new LinkedList<>(stack);
            LinkedList<T> newOut = new LinkedList<>(out);
            newOut.offerLast(newStack.pollLast());
            all_order(newIn, newStack, newOut);
        }
    }

    public static <T> void generate(LinkedList<T> in){
        all_order(in,new LinkedList<T>(),new LinkedList<T>());
    }

    public static void main(String[] args) {
//        String a=new String("123");
        LinkedList<Integer> in = new LinkedList<>();
        for (int i = 1; i <= 3; i++) {
            in.add(i);
        }
        generate(in);
    }
}
